package app.champaign;

import java.util.Arrays;

public class MergeSort{

    public static void main(String[] args) {
        int[] arr = {2,8,9,10,4,5,6,7};
        int L = 0;
        int R = 7;
        mergeSort(L, R, arr);
    }

    public static void merge(int arr[], int L, int M, int R){
        int leftSize = M - L;
        int rightSize = R - M + 1;
        int[] leftArr = new int[leftSize];
        int[] rightArr = new int[rightSize];

        //1.fill the left sub arr
        for(int i = L; i < M; i++){
            leftArr[i - L] = arr[i];
        }
        //2.fill the right sub arr
        for(int j = M; j <= R; j++){
            rightArr[j - M] = arr[j];
        }

        System.out.println("leftArr:"+Arrays.toString(leftArr)); 
        System.out.println("rightArr:"+Arrays.toString(rightArr)); 

        //merge into original arr
        int i = 0,j =0, k = L;
        while(i < leftSize && j < rightSize){
            if(leftArr[i] < rightArr[j]){
                arr[k] = leftArr[i];
                i++;
                k++;
            }else{
                arr[k] = rightArr[j];
                j++;
                k++;
            }
        }
        while(i < leftSize){
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while(j < rightSize){
            arr[k] = rightArr[i];
           j++;
            k++;
        }

        System.out.println("arr:"+Arrays.toString(arr)); 
    }

    public static void mergeSort(int L, int R, int[] arr){
        if(L == R){
            return;
        }else{
            int M = (L + R)/2;
            mergeSort(L, M  ,arr);
            mergeSort(M + 1 , R, arr);
            merge(arr, L, M +1, R);
        }
       
    }

}